{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Recherche de Cliques\n", "\n", "**Ce TP est à rendre avant le prochain cours, soit avant le 19 février à 14h15.**\n", "\n", "## Introduction\n", "\n", "En 1949, Duncan Luce et Albert Perry se demandent comment trouver des éléments de structure dans un réseau social.\n", "Une notion particulière découle de leur travail : la notion de clique, c'est à dire un groupe de personnes qui se connaissent toustes.\n", "\n", "En fait, ici, le terme \"réseau social\" est à comprendre au sens large comme un graphe qui représente les interactions entre des personnes, et le terme clique est lui-même un terme qui nous vient des sciences sociales : une clique est un ensemble de personnes qui se regroupent généralement pour des affinités ou intérêts communs.\n", "\n", "Et comme dirait un penseur contemporain local pour exprimer la forte connexion entre les membre d'une clique : \"touche à un membre de ma clique, tu verras qu'on n'est pas tout seuls\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import matplotlib.pyplot as plt\n", "import numpy as np" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## En théorie des Graphes\n", "\n", "On l'a vu en cours, dans un graphe, une clique est un sous-graphe complet d'un graphe.\n", "Par exemple, une clique de 6 sommets :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G = nx.complete_graph(6)\n", "nx.draw(G, edgecolors=\"black\", node_color=\"pink\", edge_color=\"pink\", width=4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Commençons par définir une fonction qui affiche un sous-graphe sur un graphe, qui nous sera utile par la suite. Si on ne donne pas l'argument `aretes_sous_graphe` à la fonction, elle reliera tous les sommets donnés en argument (à condition que l'arête soit aussi dans `G`), sinon elle affichera les arêtes présente dans cette liste. L'argument `with_label` permet d'afficher ou non les labels des sommets (par défaut il les affiche)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def afficher_sous_graphe(G, sommets_sous_graphe, aretes_sous_graphe=None, with_labels=True):\n", " if aretes_sous_graphe is None:\n", " aretes_sous_graphe = [(u, v) for u in sommets_sous_graphe for v in sommets_sous_graphe]\n", " aretes_sous_graphe = set(aretes_sous_graphe) & set(G.edges())\n", " \n", " Gcliques = nx.Graph()\n", " Gcliques.add_nodes_from(sommets_sous_graphe)\n", " Gcliques.add_edges_from(aretes_sous_graphe)\n", "\n", " \n", " pos = nx.spring_layout(G, seed=123)\n", " nx.draw(G, pos, edgecolors=\"black\", \n", " node_color=\"white\", width=1, with_labels=with_labels)\n", " nx.draw(Gcliques, pos, edge_color=\"pink\", edgecolors=\"black\", \n", " node_color=\"pink\", width=4, with_labels=with_labels)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut alors afficher deux sous cliques contenant respectivement $3$ et $4$ sommets." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G_exemple = nx.Graph()\n", "G_exemple.add_nodes_from(np.arange(1, 11))\n", "G_exemple.add_edges_from([(1,2),(2,3),(3,4),(1,3),(1,4),(2,4),(2,10),(3,5),(4,7),(7,8),(3,6),(6,9),(6,8),(7,8),(8,9)])\n", "\n", "sommets_clique = [1,2,3,4,6,8,9]\n", "aretes_clique = [(1,2),(2,3),(3,4),(1,3),(2,4),(1,4),(6,9),(6,8),(8,9)]\n", "\n", "\n", "afficher_sous_graphe(G_exemple, sommets_clique, aretes_clique)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Combien d'arête y a-t-il dans une clique à $n$ éléments ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Cliques Maximales\n", "\n", "Ce n'est pas très difficile de trouver une clique quelconque dans un graphe : une arête entre deux sommets forme déjà une clique de taille $2$ !\n", "\n", "C'est donc plutôt facile de trouver une clique dans un graphe, vu que n'importe quel sommet forme une clique de taille 1, et n'importe quelle arête une clique de taille 2.\n", "On va donc s'intéresser à deux types plus particuliers de cliques.\n", "\n", "**Cliques Maximales.** On dit qu'une clique est maximale dans un graphe $G$ s'il est impossible de trouver une clique plus grande en lui rajoutant des points. En d'autres termes, c'est une clique qui n'est pas un sous-graphe d'une clique plus grande.\n", "\n", "**Plus Grande Clique.** Comme il y a un nombre fini de cliques dans un graphe, il y en a nécéssairement une qui est plus grande (éventuellement ex aequo avec d'autres) que les autres dans le graphe. Cette clique est appelée la plus grande clique du graphe." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Donnez un exemple de graphe dans lequel vous expliciterez une clique maximale qui n'est pas la plus grande clique du graphe." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans ce graphe, la clique rose est une clique maximale (on ne peut pas obtenir une clique plus grande en lui rajoutant des sommets), mais ce n'est pas la plus grande car la clique bleue est une clique qui a plus d'éléments." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Rercherche de Cliques\n", "\n", "### Recherche d'une Clique Maximale\n", "\n", "Le problème de trouver une clique maximale est en fait plutôt simple : à partir d'une clique, il suffit de regarder s'il existe un sommet qui est voisin de tous les sommets de la clique. Si tel est le cas, alors on peut le rajouter à notre clique et obtenir une clique plus grande.\n", "Il suffit alors de continuer jusqu'à ne plus pouvoir ajouter de sommets à la clique obtenue : la clique est alors maximale.\n", "\n", "Pour implémenter cet algorithme, on va commencer par implémenter une fonction qui rajoute un sommet à une clique existente (si cela est possible bien sûr !).\n", "Cet algorithme est un algorithme itératif, qui prend en entrée une clique, et qui parcourt les sommets de cette clique.\n", "On dira qu'un sommet est candidat s'il est voisin de tous les sommets parcourus jusque là.\n", "\n", "Ainsi, pour le premier sommet, tous ses voisins sont candidats à agrandir la clique. On pourra alors mettre à jour cette liste à chaque sommet rencontré : les nouveaux candidats sont ceux qui étaient déjà candidats, qui sont aussi voisins du prochain sommet rencontré, et qui ne sont pas encore dans la clique. Les nouveaux candidats sont donc l'intersection des candidats et des voisins du sommet que l'on est en train de parcourir qui ne sont pas encore dans la clique.\n", "\n", "**Remarques.**\n", "* Un sommet constitue une clique à lui tout seul, on peut donc appeler la fonction en lui donnant une liste ne contenant qu'un seul sommet ;\n", "* Parfois, on aura plusieurs candidats, il suffit alors d'en choisir un.\n", "\n", "*Attention*, en prenant juste l'intersection des voisins de chacun des sommets, il est possible que l'on essaye de rajouter un sommet qui est déjà dans la clique. On prendra donc bien soin d'enlever des candidats les sommets qui sont déjà dans la clique avant de choisir un sommet à rajouter." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémentez un algorithme qui prend en entrée un graphe et une clique (ie. un ensemble de sommets) et qui renvoie `False` s'il n'est pas possible d'agrandir cette clique, et qui sinon renvoie la clique agrandie.\n", "\n", "*Indice :* en fait, plutôt que d'utiliser des listes, on utilisera des ensembles (`set` en Python). La ligne `adj = {a[0]: set(a[1]) for a in G.adjacency() }` permet de récupérer les voisins d'un sommet `s` avec `adj[s]` sous forme d'ensemble. Cela permet de calculer l'intersection de deux ensembles facilement.\n", "\n", "Vous pouvez vous référer à la documentation de python pour les ensembles. Pour cela, il suffit d'exécuter `help(set)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def agrandir_clique(G, clique):\n", " # liste d'adjacence du graphe\n", " adj = {a[0]: set(a[1]) for a in G.adjacency() }\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Essayez votre fonction sur le graphe `G_exemple` en cherchant à agrandir une clique contenant les sommets $2$ et $3$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** L'algorithme renvoie une clique, mais combien de cliques de taille 3 aurait-on pu obtenir ici ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** On peut donc maintenant implémenter une fonction qui cherche une clique maximale à partir d'un sommet donné. Implémentez la." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def clique_maximale(G, sommet):\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Recherchez une clique maximale en partant du sommet $3$ dans le graphe `G_exemple` et affichez la dans le graphe." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarque.** Si vous lancez votre fonction sur le sommet $5$, vous obtenez une clique maximale qui contient aussi le sommet $3$. Ainsi, un sommet donné peut faire partie de plusieurs cliques maximales." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Complexité.** Ici, notre implémentation n'est pas optimale car à chaque fois que l'on cherche à agrandir une clique, on recalcule les intersections entre tous les sommets, alors qu'on les a déjà calculées au coup d'avant.\n", "De plus, on pourrait représenter les voisins de chacun des sommets par un seul entier. En effet, pour un sommet $s$ donné, on pourrait représenter en binaire l'ensemble de ses voisins, le $i$-ème bit valant $1$ s'il y a une arête entre ce sommet et le sommet $i$ et $0$ sinon. Cela permettrait de calculer les intersections d'ensembles de façon très efficace, car les processeurs des ordinateurs sont très bons pour ce type d'opérations.\n", "\n", "Ainsi, même si on ne cherchera pas dans ce TP à implémenter cet algorithme de façon optimale, il est possible de l'implémenter de façon à ce qu'il s'exécute en temps linéaire en le nombre de sommets." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## k-Cliques\n", "\n", "En pratique, dans un groupe d'ami-es, il peut arriver que tous les ami-es ne soient pas tous aussi proches les un-es des autres. Notre définition de clique est donc un peu trop restrictive, car s'il manque un seul lien, la clique est tout de suite plus petite.\n", "\n", "On peut remédier à cela en utilisant une notion un peu plus large de clique : les **k-cliques**. Une k-clique est un ensemble de sommets tel qu'il existe un chemin de longueur au plus $k$ dans le graphe entre chacun de ses membres.\n", "\n", "L'algorithme que l'on a implémenté au dessus nous permet, en modifiant juste le graphe en entrée, de trouver une k-clique maximale.\n", "En fait, on va utiliser le même algorithme, mais sur un autre graphe, où l'on va rajouter des arêtes entre les sommets entre lesquels il existe un chemin de distance $k$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Recherche de 2-cliques.** Pour commencer, on va chercher des 2-cliques. Pour cela, on va créer un graphe où l'on va rajouter toutes les arêtes $(u, v)$ telles qu'il existe un sommet $s$ pour lequel les arêtes $(u, s)$ et $(s, v)$ sont dans le graphe.\n", "\n", "Pour faire cela, on peut itérer sur les sommets du graphe, et rajouter des arêtes entre chaque sommet et les voisins et ses voisins." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémentez une fonction qui prend un graphe en entrée, qui copie le graphe et qui rajoute, pour chacun des sommets, une arête entre ce sommet et chacun des voisins de ses voisins.\n", "Vous veillerez bien à ne pas rajouter directement les sommets au graphe donné en entrée, de façon à éviter de prendre en compte au cours de l'exécution de l'algorithme une arête que vous auriez vous-même ajoutée." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ajouter_chemins(G):\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Affichez le graphe obtenu en rajoutant les chemins de longueur 2 au graphe `G_simple` suivant." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G_simple = nx.Graph()\n", "G_simple.add_nodes_from([1,2,3,4])\n", "G_simple.add_edges_from([(1,2),(2,3),(3,4)])\n", "\n", "nx.draw(G_simple, with_labels=True, edgecolors=\"black\", node_color=\"pink\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut maintenant facilement faire un algorithme qui trouve des 2-cliques maximales, pour cela on procède en deux étapes :\n", "\n", "* on rajoute les chemins de longueur $2$ au graphe avec la fonction `ajouter_chemins` ;\n", "* on cherche une clique dans le graphe obtenu." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémentez une fonction qui cherche une 2-clique maximale à partir d'un sommet dans un graphe et affichez cette 2-clique sur le graphe `G_exemple` de la partie précédente." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def clique2_max(G, sommet):\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "clique2 = clique2_max(G_exemple, 2)\n", "afficher_sous_graphe(G_exemple, clique2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Que pensez-vous de la \"clique\" obtenue ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Représentation Matricielle\n", "\n", "Comme vous avez pu le voir, ce n'est pas toujours très pratique de rajouter des arêtes entre chaque sommet et les voisins de ses voisins, cela demande de faire beaucoup de boucles qui parcourent beaucoup de sommets.\n", "\n", "On pourrait rechercher des $k$-cliques en procédant comme pour les $2$-cliques, à la différence près que l'on devrait d'abord calculer récursivement le graphe où l'on aurait rajouté les chemins de longueur $k-1$, puis relier les sommets $u$ et $v$ tel qu'il existe un sommet $s$ où :\n", "\n", "* il existe un chemin de longueur $k-1$ entre $u$ et $s$ ;\n", "* l'arête $(s, v)$ est dans le graphe initial.\n", "\n", "Cette solution, si elle fonctionne, n'est pas très élégante et demande de faire beaucoup de calculs récursivement.\n", "Une meilleure solution consiste à utiliser la représentation matricielle du graphe.\n", "\n", "Pour rappel, on peut représenter un graphe à $n$ sommets sous la forme d'une matrice $M$ de taille $n \\times n$, dont l'élément $M_{i,j}$ aux coordonnées $(i, j)$ vaut $1$ s'il existe une arête entre les sommets $i$ et $j$, et $0$ sinon." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple, voilà la matrice du graphe de la partie précédente :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nx.adjacency_matrix(G).todense()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'avantage de cette représentation, c'est que si la matrice $M$ représente un graphe, le coefficient $(i, j)$ de la matrice $M \\times M$ donne directement le nombre de chemins qui vont du sommet $i$ au sommet $j$.\n", "\n", "En effet, le coefficient $(i, j)$ de $M^2$ est :\n", "\n", "$$ (M \\times M)_{i,j} = \\sum_{k=1}^n M_{i,k} M_{k, j}, $$\n", "\n", "ainsi, s'il existe un chemin entre $i$ et $k$, et entre $k$ et $j$, alors $M_{i,k} M_{k, j} = 1$, donc cela signifie qu'il existe un chemin entre les sommets $i$ et $j$ passant par $k$.\n", "\n", "On peut alors continuer à multiplier la matrice $M$ par elle-même, et la matrice $M^k = M \\times M \\times \\cdots \\times M$ ($k$ fois) contient dans chacun de ses coefficients le nombre de chemins de longueur $k$ qui relient les sommets correspondants." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarque.** La matrice $M^k$ contient les chemins de longueur $k$, mais pas ceux de longueur strictement inférieure à $k$. Pour connaître le nombre de chemins de longueur inférieure à $k$ entre deux sommets, on peut donc tout simplement sommer les matrices $M, M^2, M^3, \\dots, M^k$.\n", "\n", "Par exemple, on peut partir du graphe suivant, et afficher les graphes dont les représentations respectives sont les matrices $M^k$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "G_simple = nx.Graph()\n", "G_simple.add_nodes_from([0,1,2,3,4,5])\n", "G_simple.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,5)])\n", "M = nx.adjacency_matrix(G_simple)\n", "\n", "print(\"Graphe Original :\")\n", "print(M.todense())\n", "nx.draw(G_simple, node_color=\"pink\", edgecolors=\"black\", with_labels=True)\n", "plt.show()\n", "\n", "Mk = M\n", "for k in range(2, 5):\n", " Mk = np.dot(Mk, M)\n", " \n", " print(\"Graphe avec une arête seulement s'il existe un chemin de longueur \" + str(k) + \" entre deux sommets :\")\n", " print(Mk.todense())\n", "\n", " nx.draw(nx.from_scipy_sparse_matrix(Mk), node_color=\"pink\", edgecolors=\"black\", with_labels=True)\n", " plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémentez une fonction qui prend un graphe `G` et un entier `k` en entrée et qui :\n", "* récupère sa représentation matricielle avec `nx.adjacency_matrix(G)` ;\n", "* calcule la matrice des chemins de longueur inférieure ou égale à `k`, on pourra utiliser la fonction `np.dot` pour multiplier deux matrices ;\n", "* remplace les valeurs de la matrice obtenue de façon à ce que la valeur d'un coefficient soit $1$ s'il existe un chemin entre les sommets (ie. si la matrice calculée à l'étape précédente a un coefficient plus grand que $0$) et $0$ sinon ;\n", "* renvoie le graphe correspondant à la matrice calculée en le générant avec la fonction `nx.from_scipy_sparse_matrix`.\n", "\n", "*Attention.* La fonction `nx.from_scipy_sparse_matrix` renvoie un graphe dont les sommets ont comme noms $0, 1, 2$... on pourra donc utiliser la fonction `renommer_sommet` suivante, qui prend en entrée un graphe et les noms des sommets, et qui renvoie le graphe `G` dont les sommets ont été renommés par les noms des sommets donnés dans l'argument `nodes`." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "def renommer_sommets(G, nodes):\n", " return nx.relabel_nodes(G, {i: u for i, u in enumerate(nodes)})\n", "\n", "def graphe_chemins(G, k):\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Affichez le graphe obtenu pour le graphe de la question précédente et $k=3$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Utilisez cette fonction pour définir une fonction qui recherche des $k$-cliques maximales dans un graphe." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def kclique_max(G, k, sommet):\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Affichez une $2$-clique et une $3$-clique en partant du sommet $3$ dans le graphe `G_exemple`. Comparez la 2-clique avec le résultat obtenu dans la partie précédente." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Plus Grande Clique ?\n", "\n", "La recherche de plus grandes cliques dépasse le cadre de ce TP, et repose essentiellement sur des algorithmes de backtracking comme l'[algorithme de Bron-Kerbosch](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm), qui sont très utilisés en pratique mais dont le temps d'exécution est exponentiel en la taille du graphe.\n", "\n", "À première vue, on pourrait néanmoins se dire que, si l'on recherche une clique maximale sur chacun des sommets, puis qu'on prend la plus grande clique obtenue, on aurait une plus grande clique du graphe.\n", "\n", "**Question.** Expliquez rapidement pourquoi cette approche ne fonctionne pas." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }